﻿#pragma once
#include "Index.h"

/**
 * 二分查找
 */
class BinarySearch
{
public:
    /**
     * 二分查找.
     * 请实现无重复数字的升序数组的二分查找.
     *
	 * 给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1.
	 * 进阶：时间复杂度O(logn) ，空间复杂度O(1)
     */
    int search(std::vector<int>& nums, int target)
    {
        //非递归版本
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right)
        {
            const int mid = (left + right) / 2;
            if (nums.at(mid) == target)
                return mid;
            else if (nums.at(mid) > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return -1;
    }
    int searchInRange(std::vector<int>& nums,int left,int right,int target)
{
        if (left > right)
            return -1;
        const int mid = (left + right) / 2;
        if (nums.at(mid) == target)
            return mid;
        else if (nums.at(mid) > target)
            return searchInRange(nums, left, mid - 1, target);
        else
            return searchInRange(nums, mid + 1, right, target);
    }
public:
    /**
     * 寻找峰值.
     * 给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
	 * 1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
	 * 2.假设 nums[-1] = nums[n] =−∞
	 * 3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
	 * 4.你可以使用O(logN)的时间复杂度实现此问题吗？
     */
    int findPeakElement(std::vector<int>& nums)
    {
        if (nums.empty())
            return -1;

        const int nums_size = nums.size();
        nums.insert(nums.begin(), INT_MIN);
        nums.insert(nums.end(), INT_MIN);

        int left = 1;
        int right = nums_size;
        while (left <= right)
        {
            const int mid = (left + right) >> 1;
            const int left_val_of_mid = nums[mid - 1];
            const int right_val_of_mid = nums[mid + 1];
            const int val_of_mid = nums[mid];
            if (val_of_mid > left_val_of_mid && val_of_mid > right_val_of_mid)
                return mid - 1;
            else if (val_of_mid < right_val_of_mid)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }
public:
    /**
     * 寻找第k大.
     * 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
	 * 给定一个整数数组 a ,同时给定它的大小n和要找的k ，请返回第k大的数(包括重复的元素，不用去重)，保证答案存在。
	 * 要求：时间复杂度O(nlogn)，空间复杂度O(1)
     */
    int findKthLarge(std::vector<int> a, int n, int k)
    {
        //不合法的参数
        if (a.empty() || a.size() != n || k <= 0 || k > n)
            return -1;

        //对数组由left和right索引位置指定的范围进行第k大查找
        int left = 0, right = n - 1;
        //由pivot位置的元素进行数据划分时,
        //(pivot_range.first+1)为首个值为a[pivot]的索引位置
        //(pivot_range.second+1)为最后值为a[pivot]的索引位置
        std::pair<int, int> pivot_range;

        while (left <= right)
        {
            //随机选出划分位置
            const int pivot = left < right ? (rand() % (right - left) + left) : left;
            //划分位置上对应的值
            const int pivot_val = a[pivot];
            std::swap(a[pivot], a[right]);

            //pivot_range一开始置为无效状态,处理完后，pivot_range表示pivot_val在数组进行从大到小排序后，所在的索引位置区间
            pivot_range.first = pivot_range.second = left - 1;
            //pivot_range.first用来接收大于pivot_val的值
            //pivot_range.second用来接收等于pivot_val的值
            for (int i = left; i < right; ++i)
            {
                //大于pivot_val的值移向数据左边
                if (a[i] > pivot_val)
                {
                    pivot_range.first++;
                    std::swap(a[pivot_range.first], a[i]);
                    pivot_range.second++;
                    if (pivot_range.first != pivot_range.second)
                        std::swap(a[pivot_range.second], a[i]);
                }
                else if (a[i] == pivot_val)
                {
                    pivot_range.second++;
                    std::swap(a[pivot_range.second], a[i]);
                }
            }

            //将pivot_range变为表示pivot_val在数组中重复出现的闭区间
            pivot_range.first++;
            pivot_range.second++;
            std::swap(a[pivot_range.second], a[right]);

#ifdef DEV_TEST
            Json::Value jval;
            jval["left"] = left;
            jval["right"] = right;
            jval["kth"] = k;
            jval["pivot"] = pivot;
            jval["pivot_val"] = pivot_val;
            jval["arr"] = TestingUtil::encryptNums(a.begin() + left, a.begin() + right + 1);
            Json::StyledStreamWriter jwriter;
            jwriter.write(std::cout, jval);
#endif
            //为了寻找第k大，转换为要找的数组中的索引位置
            const int k_index = left + k - 1;
            //根据第k大的目标索引位置，判断是否位于pivot划分的区间内，在的话pivot_val就为要找的第k大值
            //不在的话，缩小[left,right]区间，进入子问题处理.
            if (k_index < pivot_range.first)
                right = pivot_range.first - 1;
            else if (k_index > pivot_range.second)
            {
                const int next_left = pivot_range.second + 1;
                k -= next_left - left;
                left = next_left;
            }
            else
                return pivot_val;// a[k_index];
        }
        return -1;
    }
};

#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(BinarySearchTest, findKthLarge)
{
    BinarySearch solution;
    {
        int kth_large = solution.findKthLarge({ 13, 11, 5, 6, 12, 13, 5 }, 7, 4);
        EXPECT_EQ(kth_large, 11);
    }

    {
        int kth_large = solution.findKthLarge({ 9,9,12,5,10,6 }, 6, 3);
        EXPECT_EQ(kth_large, 9);
    }

    {
        int kth_large = solution.findKthLarge({ 12,10,6,5,9,13,11,8,14,7,8 }, 11, 3);
        EXPECT_EQ(kth_large, 12);
    }
}
#endif